#include <stdio.h>
#include <stdlib.h>
// mac 系统上需要加 sys/ 路径才能找到该文件
// #include <sys/malloc.h>

// 声明结点的数据域类型，char 类型，别名 DataType
typedef char DataType;
// 声明结点结构
typedef struct node
{
    DataType data;     // 结点数据域
    struct node *next; // 结点指针域(自己本身)
} ListNode;

// 声明一个 ListNode 类型的指针变量(即链表)，别名为 SingleLinkList
typedef ListNode *SingleLinkList;

// 声明一个链表 别名 CircularLinkList (循环链表)
typedef ListNode *CircularLinkList;

// 声明头插法创建单链表函数
SingleLinkList createListFirst();
// 声明尾插法创建单链表函数
SingleLinkList createListLast();
// 声明带头结点的链表(尾插法)
SingleLinkList createListHasHead();

// 按结点序号。查找第i个结点
ListNode *getNodeI(SingleLinkList head, int i);
// 按结点值。查找值为k的结点
ListNode *getNodeK(SingleLinkList head, DataType k);

// 插入运算, 将x 值插入到第i个结点位置
void insertList(SingleLinkList head, int i, DataType x);
// 删除运算，将第i个结点删除
DataType deleteList(SingleLinkList head, int i);

// 打印链表的数据
void printSingleLinkList(SingleLinkList linklist);
// 打印循环链表的数据
void showLoopList(SingleLinkList linklist);

// 阅读理解
SingleLinkList exaplam(SingleLinkList L)
{
    // 假设 L = {a, b, c}
    ListNode *q, *p;
    // 至少有两个结点才会执行该条件
    if (L && L->next)
    {
        // 用指针变量 q 指向 L 地址，此时 q = {a, b, c}
        q = L;
        // L 指针指向 L 的下一个结点，此时 L = {b, c}
        L = L->next;
        // p 指针指向 L 的地址，此时 p = {b, c}
        p = L;
        // 用指针变量p查找链表的尾结点
        while (p->next)
        {
            p = p->next;
        }
        // 循环判断 p 是否有下一个结点，并将p指向p的下个结点，即 c 结点，此时 p = {c}
        // 将第一个结点连接到链表的尾部，作为新的尾结点。
        // 将p的下一个结点指向 q，此时 p = {c, a, b, c} ==> 循环链表
        p->next = q;
        printf("=====\n");
        showLoopList(p);
        printf("=====\n");
        // 将 q 的下一个结点置为 NULL， 则 q = {a}， p = {c, a}
        q->next = NULL;
    }
    // 此前 L = {b, c}， 由于原本p指针指向L变成指向c结点，而c结点的下一个结点为a， 故最后 L = {b, c, a}
    return L;
};

// 将带头结点a的链表A 分解为 A 和 B 两个链表，其头指针分别为 a，b。链表A中序号为奇数，B中为偶数
void split(SingleLinkList A, SingleLinkList B)
{
    // 假设 A = { 头, a, b, c}; B={ 头 }
    // p 指向表头结点， p负责扫描整个链表, 此时 p = {a, b, c}
    ListNode *p = A->next;
    // r 指向A表的当前结点，此时 r = { 头, a, b, c}
    ListNode *r = A;
    // s 指向B表的当前结点, 此时 s = { 头 }
    ListNode *s = B;
    while (p != NULL)
    {
        // 序号为奇数的结点链接到A表上，此时 A = { 头, a, b, c}；r = { 头, a, b, c}
        // 下一次循环 r = {a}, p = {c}. 将 a 结点下个指向 c 结点，即  A = { 头, a, c}
        r->next = p;
        // r 总是指向A链表的最后一个结点，此时 r = {a, b, c}
        // 下一次循环 r = {c}
        r = p;
        // p 指向原链表A 中的偶数序号结点，此时 p = {b, c}
        // 下一次循环 p = NULL, 不走 if 逻辑
        p = p->next;
        if (p)
        {
            // 序号为偶数数的结点链接到B表上(也就是将 B 头结点的下一个结点连接到 p)
            // B = { 头, b, c}；s = { 头, b, c}
            s->next = p;
            // s = {b, c}
            s = p;
            // 奇数结点，p = {c}
            p = p->next;
        }
        // r，s 中后面的结点置为 null 且也改变A\B中的结点指向, 此时 r = {a}, s={b}; A = { 头, a}, B = { 头, b}
        // 下一次循环 r = NULL, s=NULL. 最终 A = { 头, a, c}, B = { 头, b}
        r->next = s->next = NULL;
    }

    // printf("============A==========\n");
    // printSingleLinkList(A);
    // printf("============B==========\n");
    // printSingleLinkList(B);
    // printf("======================\n");
}
// 将两个带头结点链表A、B(两链表节点数据值递增有序) 合并为 C
SingleLinkList merge(SingleLinkList A, SingleLinkList B)
{
    // pa、pb 分别指向两个链表的开始结点
    ListNode *pa = A->next;
    ListNode *pb = B->next;

    ListNode *pc;
    // 用 A链表的头结点作为 C链表的头结点
    SingleLinkList C = pc = A;
    while (pa != NULL && pb != NULL)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    // 插入剩余的部分
    pc->next = (pa != NULL) ? pa : pb;
    // 释放 B 链表
    free(B);
    return C;
}

// 删除带头结点的非空链表最小值的结点， 实际就是双指针移动
void deleteMinValueHead(SingleLinkList *L)
{
    ListNode *cur = (*L)->next;
    ListNode *prev = (*L);

    ListNode *minNode = cur;
    ListNode *minPrev = prev;

    // 找出具有最小值的结点及其前一个结点
    while (cur != NULL)
    {
        printf("cur-data=%c, min-data=%c\n", cur->data, minNode->data);
        if (cur->data < minNode->data)
        {
            minNode = cur;
            minPrev = prev;
        }
        prev = cur;
        cur = cur->next;
    }
    // 删除最小结点
    minPrev->next = minNode->next;
    free(minNode);
}
// 不带头结点的非空链表
void deleteMinValue(SingleLinkList *L)
{
    ListNode *cur = (*L);
    ListNode *prev = NULL;

    ListNode *minNode = (*L);
    ListNode *minPrev = NULL;

    // 找出具有最小值的结点及其前一个结点
    while (cur != NULL)
    {
        printf("cur-data=%c, min-data=%c\n", cur->data, minNode->data);
        if (cur->data < minNode->data)
        {
            minNode = cur;
            minPrev = prev;
        }
        prev = cur;
        cur = cur->next;
    }

    // 删除最小结点
    if (minPrev == NULL)
    {
        // 最小结点为开始结点
        *L = (*L)->next;
    }
    else
    {
        minPrev->next = minNode->next;
    }
    free(minNode);
}

int main()
{
    // SingleLinkList firstLink = createListFirst();
    // printSingleLinkList(firstLink);

    // SingleLinkList lastLink = createListLast();
    // printSingleLinkList(lastLink);
    // printf("=======\n");
    // SingleLinkList aa = exaplam(lastLink);
    // printSingleLinkList(aa);
    // exit(0);

    SingleLinkList hasHeadLink = createListHasHead();
    // SingleLinkList hasHeadLink = createListLast();
    printSingleLinkList(hasHeadLink);

    // deleteMinValueHead(&hasHeadLink);
    // deleteMinValue(&hasHeadLink);

    // printSingleLinkList(hasHeadLink);

    // exit(0);

    // 带头结点分割
    // SingleLinkList head = (ListNode *)malloc(sizeof(ListNode));
    // split(hasHeadLink, head);
    // exit(0);
    // 带头结点链表合并
    // SingleLinkList bHead = createListHasHead();
    // printSingleLinkList(bHead);
    // SingleLinkList mergeList = merge(hasHeadLink, bHead);
    // printf("=========merge========\n");
    // printSingleLinkList(mergeList);
    // exit(0);

    // printf("========find element by order=====\n");
    // int orderNum = 1;
    // ListNode *nodei = getNodeI(hasHeadLink, orderNum);
    // if (nodei != NULL)
    // {
    //     printf(">> find element by order number: num=%d, value=%c\n", orderNum, nodei->data);
    // }

    // printf("========find element by value=====\n");
    // char value = 'c';
    // ListNode *nodek = getNodeK(hasHeadLink, value);
    // if (nodek != NULL)
    // {
    //     printf(">> find element by values: p=%p, value=%c\n", nodek, nodek->data);
    // }
    // else
    // {
    //     printf(">>error! not found element value=%c", value);
    // }

    printf("\n==============insert element==========\n");
    insertList(hasHeadLink, 2, '6');
    printSingleLinkList(hasHeadLink);

    printf("\n==============delete element==========\n");
    deleteList(hasHeadLink, 2);
    printSingleLinkList(hasHeadLink);
    return 0;
}

// 循环链表打印
void showLoopList(CircularLinkList p)
{
    CircularLinkList temp = p;
    do
    {
        printf("v=%c\n", temp->data);
        temp = temp->next;
    } while (temp != p);
}

// 打印链表-单链表
void printSingleLinkList(SingleLinkList linklist)
{
    printf("---------start print element of list---------\n");
    SingleLinkList item = linklist;
    if (item == NULL)
    {
        printf(">>>it is empty list\n");
        return;
    }

    while (item != NULL)
    {
        printf("value=%c\n", item->data);
        item = item->next;
    }
}

SingleLinkList createListFirst()
{
    // 置空链表
    SingleLinkList head = NULL;
    ListNode *p;
    // 读取字符
    char ch = getchar();
    while (ch != '\n')
    {
        // 分配ListNode类型的结点的地址空间，并将其首地址存入指针变量p中
        p = (ListNode *)malloc(sizeof(ListNode));
        // 数据域赋值
        p->data = ch;
        // 指针域赋值
        p->next = head;
        // 头指针指向下一个结点. 最后插入的结点总是链表的头结点
        head = p;
        // 读取下一个字符
        ch = getchar();
    }
    // 返回链表的头指针
    return head;
}

SingleLinkList createListLast()
{
    // 置空列表
    SingleLinkList head = NULL;

    ListNode *tail;
    ListNode *p;
    char ch;
    while ((ch = getchar()) != '\n')
    {
        p = (ListNode *)malloc(sizeof(ListNode));
        p->data = ch;
        // 空链表时，将新结点(第一个)作为头结点
        if (head == NULL)
        {
            head = p;
        }
        else
        {
            // 新结点作为尾结点的下一个结点
            tail->next = p;
        }
        // 尾指针指向新的尾结点
        tail = p;
    }

    // 终端结点的指针域置空。已经是最后一个结点，则下一个指针域为 NULL
    if (tail != NULL)
    {
        tail->next = NULL;
    }
    return head;
}

SingleLinkList createListHasHead()
{
    // 申请头结点，分配空间. 头结点不设置数据
    SingleLinkList head = (ListNode *)malloc(sizeof(ListNode));
    head->data = 'H';

    ListNode *tail = head;
    ListNode *p;
    char ch;
    while ((ch = getchar()) != '\n')
    {
        // 申请新结点
        p = (ListNode *)malloc(sizeof(ListNode));
        p->data = ch;
        // 新结点链接的尾结点
        tail->next = p;
        // 尾指针指向新结点
        tail = p;
    }

    // 终端结点指针域置空
    tail->next = NULL;

    return head;
}

ListNode *getNodeI(SingleLinkList head, int i)
{
    // 带头结点列表，使 p 指向第一个结点
    ListNode *p = head->next;

    int j = 1;
    // 结点不为 null 并且有下一个结点
    while (p != NULL && p->next != NULL && j < i)
    {
        p = p->next;
        j++;
    }

    if (j == i)
    {
        return p;
    }
    printf(">>error! not found the order number: order=%d\n", i);
    return NULL;
}

ListNode *getNodeK(SingleLinkList head, DataType k)
{
    ListNode *p = head->next;
    // 循环查找等于k的结点
    while (p != NULL && p->data != k)
    {
        p = p->next;
    }

    return p;
}

void insertList(SingleLinkList head, int i, DataType x)
{
    // 将p指向带头结点指针的单链表
    ListNode *p = head;
    // 定义新结点
    ListNode *newNode;

    int j = 0;
    while (p != NULL && i - 1 > j)
    {
        // 使p指向第 i-1 个结点
        p = p->next;
        j++;
    }
    // 插入的位置 在链表大小范围外时，无后续结点
    if (p == NULL)
    {
        printf("error! unable to insert \n");
        return;
    }

    // 申请新结点空间
    newNode = (ListNode *)malloc(sizeof(ListNode));
    // 新结点数据域赋值
    newNode->data = x;
    // 将新结点的下一个结点指向 原结点(i-1)的下一个结点(i)
    newNode->next = p->next;
    // 将原结点(i-1)的下一个结点指向新结点
    p->next = newNode;
}

DataType deleteList(SingleLinkList head, int i)
{
    // 将p指向带头结点指针的单链表
    ListNode *p = head;
    // 定义结点保存要删除的那个结点
    ListNode *s;

    int j = 0;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    if (p == NULL)
    {
        printf("error! unable to delete \n");
        exit(0);
    }
    // 将s指向第i个结点，即 要删除的那个结点
    s = p->next;
    // s->next 相当于 p->next-next
    p->next = s->next;
    DataType x = s->data;
    // 释放要删除的结点
    free(s);

    return x;
}
